package 强化训练;

public class day18字符串通配符 {
    public static void main(String[] args) {
        String s = "aa";
        String p = "*";
        day18字符串通配符 o = new day18字符串通配符();
        System.out.println(o.isMatch(s, p));
    }
    public boolean isMatch(String s, String p) {
        int slen = s.length();
        int plen = p.length();
        boolean[][] dp = new boolean[plen+1][slen+1];
        dp[0][0] = true;
        //数组的第一行和第一列分别表示空串“”；
        //basecase：空串和空串和*匹配为true，其他都为fasle
        for(int i = 0;i <slen ;i ++){
            if(' ' == s.charAt(i) || s.charAt(i) == '*'){
                dp[0][i+1] = true;
            }
        }
        for(int i = 0;i < plen; i++){
            if(' ' == p.charAt(i) && p.charAt(i) != '*'){
                dp[i+1][0] = true;
            }else if (p.charAt(i) == '*'){
                dp[i+1][0] = dp[i][0];
            }
        }

        //开始填表
        for(int i = 1 ;i < plen + 1 ; i++){
            char c = p.charAt(i-1);
            for(int j = 1;j < slen + 1;j++){
                //先判断当前元素是否为*
                if(c == '*'){
                    dp[i][j] = dp[i-1][j] || dp[i][j-1];
                }else if(c == '?'){
                    dp[i][j] = dp[i-1][j-1];
                }else{
                    char ch = s.charAt(j-1);
                    if(c == ch){
                        dp[i][j] = dp[i-1][j-1];
                    }
                }
            }
        }
        return dp[plen][slen];
    }
}
